package 数据结构;

import java.util.ArrayList;
import java.util.List;

public class Trie {
    /** Initialize your data structure here. */
    List<String> list;
    public Trie() {
         list = new ArrayList<>();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        list.add(word);
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
          return list.contains(word);
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        for (String s : list) {
            if (prefix.length()>s.length())
                continue;
            if (s.substring(0,prefix.length()).equals(prefix))
                return true;
        }
        return false;
    }
}
